1690F - Shifting String - CodeForces Solution

// Problem: F. Shifting String
// Contest: Codeforces - Codeforces Round #797 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1690/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define pb push_back
#define endl '\n'
#define mod 1000000007
#define N 500005
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define control ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long int
#define ffor(i, n) for(int i=0; i<n; i++)
#define fforr(i, n) for(int i=1; i<=n; i++)
#define rfor(i, n) for(int i=n-1; i>=0; i--)
#define rforr(i, n) for(int i=n; i>0; i--)
#define all(x) x.begin(), x.end()
#define F  first
#define S  second
#define inf 9223372036854775807
using namespace std;
void setIO()
{	
	control;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}
void print(bool chk){
	if(chk){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}
int min(int a, int b){
	return a>b?b:a;
}
int max(int a, int b){
	return a<b?b:a;
}
int power(int x,int y,int p)
{
    int ans=1;
    x=x%p;
    if(x==0)
    {
    	return 0;
    }
    while(y>0)
    {
        if(y&1)
        {
        	ans=(ans*x)%p;
        }
        y=y>>1;
        x=(x*x)%p;
    }
    return ans;
}
int32_t main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		string s; cin >> s;
		vi v(n);
		ffor(i, n){
			cin >> v[i];
			v[i]--;
		}
		vi vis(n);
		vi res;
		ffor(i, n){
			if(!vis[i]){
				vi temp;
				temp.pb(i);
				vis[i] = 1;
				int x = v[i];
				while(x != i){
					vis[x] = 1;
					temp.pb(x);
					x = v[x];
				}	
				int d = temp.size();
				bool test = 0;
				int mn = INT_MAX;
				for(int j=1; j*j<=d; j++){
					if(d%j == 0){
						int l = j, r = d/j;
						bool flag = 1;
						for(int k=0; k<l; k++){
							for(int p=k+l; p<d; p+=l){
								if(s[temp[p]] != s[temp[k]]){
									flag = 0;
									break;
								}
							}
							if(!flag)break;
						}
						if(flag){
							mn = min(mn, l);
						}
						flag = 1;
						for(int k=0; k<r; k++){
							for(int p=k+r; p<d; p+=r){
								if(s[temp[p]] != s[temp[k]]){
									flag = 0;
									break;
								}
							}
							if(!flag)break;
						}
						if(flag){
							mn = min(mn, r);
						}
					}
					
				}
				res.pb(mn);
			}
		}
		int ans = 1;
		for(int x:res){
			ans = ans*x/__gcd(ans, x);
		}
		cout << ans << endl;
	}
}